Graph

I. Mathematik:Graphische Darstellung einer ⇡ Funktion im ⇡ Koordinatensystem.

II. Operations Research:1. Begriff: Ein G. besteht aus einer nichtleeren Menge von V und einer Menge E mit V ∩ E = 0 sowie einer auf E definierten Abbildung w, die jedem Element k aus E genau ein Paar i und j von Elementen aus V zuordnet. Wird auch als Netzwerk bezeichnet.

- 2. Typen: a) Ungerichteter G.: Das jedem Element k ∈ E zugewiesene Paar von Elementen aus V ist nicht geordnet. Die Elemente von E werden Kanten genannt.

- b) Gerichteter G.: Das jedem Element p ∈ E zugewiesene Paar von Elementen aus V ist geordnet (p = (i, j)). Ein Knoten i heißt Vorgänger bzw. Nachfolger des Knoten j, falls ein Pfeil (i, j) bzw. (j, i) existiert. Vorgänger und Nachfolger werden als Nachbarn bezeichnet.

- Vgl. auch ⇡ Flussgraph, ⇡ bewerteter Digraph.

- 3. Schreibweise: Bei der Schreibweise wird auf die Angabe der Inzidenzabbildung verzichtet. Sie wird implizit berücksichtigt, indem E als Menge von nicht geordneten oder geordneten Knotenpaaren angegeben wird. Ein ungerichteter G. wird mit G (V, E), ein gerichteter G. mit G (V, E) beschrieben.

- 4. Darstellung: Anschaulich kann jeder Knoten geometrisch mit einem Punkt oder Kreis und jede Kante (bzw. jeder Pfeil) mit einer Verbindungslinie (bzw. gerichteten Verbindungslinie) zwischen den zugeordneten Knoten identifiziert werden. Diese geometrische Darstellung eines G. nennt man Diagramm bzw. Pfeildiagramm.